package LeetCode.exercise;

//import javafx.util.Pair;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LC662 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {

    }
    class Type <K, V>{
        K key;
        V value;
        public Type(K key, V value){
            this.key = key;
            this.value = value;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        List<Type<TreeNode, Integer>> queue = new ArrayList<>();
        int res = 0;
        queue.add(new Type<TreeNode, Integer>(root, 1));
        while(!queue.isEmpty()){
            Type<TreeNode, Integer> first = queue.get(0);
            Type<TreeNode, Integer> end = queue.get(queue.size()-1);
            res = Math.max(res, end.value - first.value + 1);
            List<Type<TreeNode, Integer>> tmp = new ArrayList<>();
            for(Type<TreeNode, Integer> type: queue){
                if(type.key.left != null){
                    tmp.add(new Type<>(type.key.left, type.value * 2));
                }
                if(type.key.right != null){
                    tmp.add(new Type<>(type.key.right, type.value * 2 + 1));
                }
            }
            queue = tmp;
        }
        return res;
    }
}
